package demo03;


import java.util.Arrays;

public class QuickSort01 {
    public static void main(String[] args) {
        int[] a = {5,3,7,2,9,8,1,4};
        quickSort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static int partition(int[] a, int l, int h) {
        int pivot = a[h];
        int i = l;
        for (int j = l; j < h; j++) {
            if (a[j] < pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, h); // 将枢轴元素移至正确位置
        return i;
    }

    public static void quickSort(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h); // 使用正确的左边界
        quickSort(a, l, p - 1); // 左分区
        quickSort(a, p + 1, h); // 右分区
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    //单边循环快排
    //每轮排序选择一个基准点pivot,让小于基准点的进入一个分区,大于基准点的进入另一个分区
    //当分区完成时,基准点元素位置就是其最终的位置
    //在子分区 重复以上步骤,直至子分区元素小于1,体现分而治之的思想
    /*
    单边循环快排:
    (1) 选择最右元素作为基准点的元素
    (2)j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
    (3) i 指针维护小于基准点元素的边界，也是每次交换的目标索引
    (4) 最后基准点与i交换,i即为分区的位置
     */






}
